package cn.njupt.cmpSort;
//荷兰国旗快排编写
public class QuickSort2<E extends Comparable<E>> extends Sort<E>{
    @Override
    public void sort() {
        sort(0,array.length);
    }

    private void sort(int begin, int end) {
        if(end-begin<2)return;

        int[] indexs=partition(begin,end,array[begin]);
        sort(begin,indexs[0]+1);
        sort(indexs[1],end);

    }

    private int[] partition(int begin, int end, E target) {
        int[] result=new int[2];

        int left=begin-1;
        while(begin<end){
            if(cmpElements(array[begin],target)>0){
                swap(begin,--end);
            }else if(cmpElements(array[begin],target)<0){
                swap(++left,begin++);
            }else{ //array[begin]==target
                begin++;
            }
        }
        result[0]=left;
        result[1]=begin;
        return result;
    }
}
